package leetcode.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author wangmaolin1
 * @date 2021/12/5 下午3:58
 */
public class _145后序遍历 {

    public static List<Integer> lastorderRecruse(TreeNode root) {
        List<Integer>result=new ArrayList<>();
        if (root==null){
            return  result;
        }
        doPostOrder(result,root);
        return  result;
    }

    private static void doPostOrder(List<Integer> result, TreeNode root) {
        if (root==null){
            return;
        }
        doPostOrder(result,root.left);
        doPostOrder(result,root.right);
        result.add(root.val);
    }

    /**
     * 迭代 后序遍历
     *
     * @param root
     * @return
     */
    public static List<Integer> lastorderIterate(TreeNode root) {
        LinkedList<Integer>result=new LinkedList<>();
        if (root==null){
            return result;
        }
        Deque<TreeNode> stack=new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode cur = stack.pop();
            result.addFirst(cur.val);
            if (cur.left !=null){
                stack.push(cur.left);
            }
            if(cur.right!=null){
                stack.push(cur.right);
            }
        }
        return result;

    }

    /**
     * morris 解决后序遍历 morris 的核心思想是找到当前遍历顺序的前驱节点，对于后序遍历，某个节点的前驱节点
     *
     * @param root
     * @return
     */
    public static List<Integer> lastorderMorris(TreeNode root) {
        return null;
    }

    public static void main(String[] args) {
        /*
              0
           1    2
              3    4
         */
        TreeNode treeNode = new TreeNode(0);
        treeNode.left = new TreeNode(1);
        treeNode.right = new TreeNode(2);
        treeNode.right.left = new TreeNode(3);
        treeNode.right.right = new TreeNode(4);
        List<Integer> list = lastorderIterate(treeNode);
        System.out.println(list);
    }
}
